/**
 * FileName: answer_1
 * Author:   why
 * Date:     2019/3/13 11:39
 * Description:
 */
package algorithm.leetcode.problem_332;

import java.util.Arrays;

public class answer_1 {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        if (amount <= 0) return -1;
        return coindp(coins, amount);
    }


    /**
     * 状态：金额
     * 转移：一个硬币，这个硬币的金额在coins[]数组中遍历
     * dp函数：输入金额，返回最少硬币数
     *
     * @param coins
     * @param amount
     * @return
     */
    public int coindp(int[] coins, int amount) {
        //最多的硬币情况是全部是1元，共有amount个硬币，共有amount+1个状态，amount+1个金额
        int[] dp = new int[amount + 1];
        //必须将所有的dp赋最大值，因为要找最小值
        Arrays.fill(dp, amount + 1);
        //自底向上，金额为0，最小硬币数为0
        dp[0] = 0;
        int[] mem = dp;
        for (int am = 1; am <= amount; am++) {
            //遍历coins的金额
            for (int coin : coins) {
                //am-coin 必须大于0，否则数组溢出
                if (am >= coin) {
                    //金额为11的最小硬币数 和 金额为(11-一个面值)的最小硬币数+1 比较最小值
                    dp[am] = Math.min(dp[am], dp[am - coin] + 1);
                }

            }
        }
        //返回金额为amount的最小硬币数 根据测试用例判断dp[amout]>amount
        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {

    }

}
